#include<iostream>
#include<vector>
using namespace std;

//leetcode23

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
 
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty())
            return nullptr;
        bool flag = true;
        ListNode* head = nullptr, * cur = nullptr;
        int sz = lists.size();
        while (flag)
        {
            flag = false;
            ListNode* midNum = nullptr;
            int midNumPos = 0;
            for (int i = 0; i < sz; ++i)
            {
                if (lists[i] != nullptr)
                {
                    if (flag == false)
                        flag = true;
                    if (midNum == nullptr)
                    {
                        midNum = lists[i];
                        midNumPos = i;
                    }
                    else
                    {
                        if (lists[i]->val < midNum->val)
                        {
                            midNum = lists[i];
                            midNumPos = i;
                        }
                    }
                }
            }

            if (head == nullptr)
            {
                head = midNum;
                cur = midNum;
            }
            else
            {
                cur->next = midNum;
                cur = cur->next;

            }
            if (lists[midNumPos] != nullptr)
                lists[midNumPos] = lists[midNumPos]->next;
        }
        return head;
    }
};